#include <iostream>
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;

void printTable(const vector<vector<int>>& matr) {
	printf("   ");
	for (int j = 0; j < matr[0].size(); ++j) {
		printf("%3d", j);
	}
	printf("\n");
	
	for (int i = 0; i < matr.size(); ++i) {
		printf("%3d", i);
		for (int j = 0; j < matr[i].size(); ++j) {
			printf("%3d", matr[i][j]);
		}
		printf("\n");
	}
}

int main() {
	// your code goes here
	int n, C;          // Число предметов и максимальный вес
	cin >> n >> C;
	vector<int> c(n+1), w(n+1);   // Стоимость предметов и их веса
	vector<vector<int>> matr(n+1, vector<int>(C+1));
	for (int i = 1; i <= n; ++i) {
		cin >> c[i] >> w[i];
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j <= C; ++j) {
			if (j < w[i]) matr[i][j] = matr[i-1][j];
			else matr[i][j] = max(matr[i-1][j], matr[i-1][j-w[i]] + c[i]);
		}
	}
	printTable(matr);
	return 0;
}